"""算法思想可查看下面链接
https://www.bilibili.com/video/BV1Ag41117YU/?spm_id_from=333.337.search-card.all.click
"""

from collections import deque


class TrieNode:
    __slots__ = ['son', 'fail', 'is_end', 'word']

    def __init__(self):
        self.son = {}  # 子节点
        self.fail = None  # 失败指针
        self.is_end = False  # 是否为单词结尾
        self.word = None  # 如果是结尾，存储对应的单词


class ACAutomaton:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        """插入一个单词到Trie树中"""
        node = self.root
        for char in word:
            if char not in node.son:
                node.son[char] = TrieNode()
            node = node.son[char]
        node.is_end = True
        node.word = word

    def build_fail(self):
        """构建失败指针，BFS遍历"""
        queue = deque()
        self.root.fail = None
        queue.append(self.root)
        # 使用bfs 遍历当前节点的所有子节点（char是当前节点字符，child_node是对应的子节点）
        while queue:
            current_node = queue.popleft()
            # char,son_node 表示为 当前节点的儿子节点信息
            for char, son_node in current_node.son.items():
                print("char", char)
                if current_node == self.root:
                    # 根节点的所有子节点的失败指针都指向根节点本身
                    son_node.fail = self.root

                else:
                    # 从当前节点的失败指针开始查找
                    p = current_node.fail
                    print(char,p)
                    # 循环直到找到匹配或者到达根节点
                    while p is not None:
                        # 检查当前失败指针节点是否有相同的字符子节点,当前值在 p的子节点里面出现
                        if char in p.son:
                            # 找到匹配，设置子节点的失败指针
                            son_node.fail = p.son[char]
                            break
                        # 继续向上查找
                        p = p.fail
                        print("p.fail",p)

                    # 如果查找到根节点仍然没有找到匹配
                    if p is None:
                        # 将子节点的失败指针指向根节点
                        son_node.fail = self.root

                # 将当前子节点加入队列，以便后续处理它的子节点
                queue.append(son_node)

    def search(self, text):
        """在文本中搜索所有出现的模式"""
        result = []
        current_node = self.root

        for i, char in enumerate(text):
            while char not in current_node.son and current_node != self.root:
                current_node = current_node.fail

            if char in current_node.son:
                current_node = current_node.son[char]
            else:
                current_node = self.root

            # 检查当前节点及其失败路径上的所有节点是否为单词结尾
            temp = current_node
            while temp != self.root:
                if temp.is_end:
                    result.append((i - len(temp.word) + 1, i, temp.word))
                temp = temp.fail

        return result

# 使用示例
if __name__ == "__main__":
    ac = ACAutomaton()

    # 添加需要匹配的关键词
    keywords = ["he", "she", "her", "say"]
    for word in keywords:
        ac.insert(word)

    # 构建失败指针
    ac.build_fail()

    # 搜索文本
    text = "sherhsay"
    matches = ac.search(text)

    print(f"在文本 '{text}' 中找到以下匹配:")
    for start, end, word in matches:
        print(f"位置 {start}-{end}: {word}")